1. Field of the Invention
The invention relates to digital filters performing processing on a frequency domain function that corresponds to zeroing a portion of a time domain signal obtained by the inverse transform of such a frequency domain function.
Such a frequency domain function can be frequency response, i.e. the transfer function of a filter, e.g. an adaptive filter, or it can be the Fourier transform of a time domain signal.
2. Description of Related Art
In conventional manner, a digital filter performs operations on data that can either be data that is directly available at an input or an output of the filter, or else data that is obtained by applying a transform such as the Fourier transform, the Hartley transform, or some other transform.
Use of such transforms, frequently implemented by means of fast algorithms, serves to reduce very considerably the number of arithmetical operations that need to be performed to process the data.
Digital processing apparatus is often designed to perform convolution or correlation operations. Numerous applications based on adaptive processing of the signal thus require convolution (filtering) and correlation operations to be performed, which operations are performed on vectors having data or coefficients that are variable, said vectors often being large in size (several hundreds to several thousands of coefficients).
In the field of telecommunications, acoustic and electrical echo cancelling, removing noise from speech, and transmission channel equalization, and in other fields, applications such as adaptive control, all make use of such techniques for adaptively processing a signal.
Calculating a convolution or a correlation exactly often requires a constraint to be applied on the size of the time domain vector representing the filter or the data, i.e. a limit on the number of non-zero samples in the inverse transform of the frequency domain vector that is to be used, regardless of whether this frequency domain vector is the frequency response of a filter or the transform of a time domain signal that is to be processed.
This constraint is conventionally implemented by applying an inverse transform on the data in the transform domain, i.e. the frequency domain, and then applying windowing that eliminates certain components of the time domain vector, and finally applying the forward transform so as to obtain the exact result in the transform domain.
When it is desired to make an optimum filter for application to a signal that is subject to disturbance, for example noise or echo, it is common practice to calculate the transfer function of the optimum filter from the affected signal, using some number of frequency domain points in the transform of the signal that is smaller than the total number of points of the signal.
In addition, since the frequency domain vector of the filter is short, exact computation of the output signal of the filter which needs to be performed by linear convolution often assumes that the impulse response of the optimum filter is extended by zeros.
That operation of computing a long frequency response filter on the basis of a short frequency response filter by extending the impulse response of the filter with zeros is usually performed, yet again, by an intermediate passage through the time domain, extending the impulse response of the filter with zeros, and a forward transform so as to obtain the exact result in the transform domain.
It will be understood that passing into the time domain in this way in order to apply constraint zeros, or indeed to extend the impulse response of an optimum filter by means of zeros, is expensive in terms of computation since it requires two transforms to be performed (a forward transform and an inverse transform).
The theoretical bases showing the typical reasons why such constraints are often necessary are described below:
The advantage of using a Fourier transform (FT) for filtering or for computing correlation stems from the fact that in the transform domain convolution and correlation operations are represented merely by multiplications. The description below relates solely to convolution, but correlation is entirely analogous thereto.
Let h(n) be a filter of length Lh, and x(n) an input signal to the filter. The output of the filter is then written:       y    ⁡          (      n      )        =                    x        ⁡                  (          n          )                    *              h        ⁡                  (          n          )                      =                            ∑                      i            =            0                                              L              h                        -            1                          ⁢                              h            ⁡                          (              i              )                                ⁢                      x            ⁡                          (                              n                -                i                            )                                          =              IFT        ⁡                  [                                    FT              ⁡                              [                                  x                  ⁡                                      (                    n                    )                                                  ]                                      ·                          FT              ⁡                              [                                  h                  ⁡                                      (                    n                    )                                                  ]                                              ]                    where FT[ . . . ] and IFT[ . . . ] designate the forward Fourier transform and the inverse Fourier transform, and where * designates the convolution operation. In practice, two difficulties prevent the above equation being used directly:                in order to calculate the Fourier transform of the signal, it is necessary to know the signal in full, i.e. all past and future samples, and that is not possible; and        in numerous applications such as echo cancelling or adaptive filtering, the filter h(n) varies in time.        
To resolve those problems, the person skilled in the art subdivides the signal into blocks of length N and associates each block b with a filter hb(n) of length Lh. In the general case, such blocks overlap. In order to simplify notation, it is assumed that the blocks are juxtaposed, but this condition is not necessary.
Let:             x      b        ⁡          (      n      )        =      {                                                                      x                ⁡                                  (                                      n                    +                    bN                                    )                                            ⁢                                                          ⁢              if              ⁢                                                          ⁢              0                        ≤            n            ≤                          N              -              1                                                                        0            ⁢                                                  ⁢            elsewhere                              
The output signal y(n) is given by:       y    ⁡          (      n      )        =                    ∑                  b          =                      -            ∞                          ∞            ⁢                                    y            b                    ⁡                      (                          n              -              bN                        )                          ⁢                                  ⁢        with        ⁢                                  ⁢                              y            b                    ⁡                      (            n            )                                =                            x          b                ⁡                  (          n          )                    *                        h          b                ⁡                  (          n          )                    
In order to calculate the forward and inverse Fourier transforms, a fast method is used known as the “fast Fourier transform” (FFTT for a forward transform on T points, IFFTT for the inverse transform on T points).
The signal yb(n) is zero for n<0 and n≧T=N+Lh−1, which means that the minimum number of points for calculating the transforms is equal to T. It can be proved that for 0≦n≦T−1, the following is obtained:yb(n)=IFFTT[FFTT[xb(n)]·FFTT[hb(n)]]=IFFTT[Xb,T(k)·Hb,T(k)]
In some cases, there is no need for all of the values of yb, but only for Ly consecutive points. In which case, the size of the FFTs must satisfy:T≧0.5*(N+Lh+Ly−1)
This constraint is known as the linear convolution constraint.
In practice, the following problem is often encountered:
N (the size of a data block), T (the size of the FFT), and Ly (the working length of the result) are set. X(k) is computed by the FFT and the filter H(k) by some arbitrary method directly in the transform domain on T points. The two factors for multiplication are thus available, but the condition that is necessary to ensure that filtering is correct:Lh≦2T−N−Ly+1is not satisfied. The question is how to obtain a filter {tilde over (H)}(k) in the transform domain which is an approximation to Hb,T(k), but which also satisfies the constraint. In the prior art, the inverse transform of H is computed, a portion of the signal is set to zero, and a forward transform of said extended function is recomputed in order to replace H.
Another problem is also very frequently encountered. It is as follows:
N (the size of a data block), T (the size of the FFT), and Ly (the useful length of the result) are set. X(k) is calculated by the FFT and the filter H(k) by some arbitrary method directly in the transform domain on L=T/D≦2T−N−Ly+1 points. The question is how to obtain a filter {tilde over (H)}(k) in the transform domain on T points instead of L which is an interpolation of H(k) and which satisfies the constraint Lh≦2T−N−Ly+1.
In the prior art, the inverse transform of H is computed, it is extended with zeros, a new function H is recomputed on the basis of the truncated inverse transform, and then by means of a forward transform.
When there is a zero constraint, proposals have been made to avoid passing in this way via two successive transforms which are expensive in computation by means of processing (filtering) performed directly in the transform domain on the frequency domain data.
When cancelling an acoustic echo, and more precisely in the field of block adaptive filters using the Fourier transform, frequently known as frequency domain adaptive filters (FDAF), Clark et al. [1] describe a general formalism from which it can be seen that it is necessary to apply a constraint on the length of the impulse response of the adaptive filter in order to obtain an exact algorithm, and they propose implementing convolution with the frequency response of the filter that is equivalent to multiplying by a window in the time domain. The number of coefficients in the proposed convolution is very high, thus maintaining very complex computation.
Sommen et al. [5] describe another variant of FDAF in which the time constraint is implemented by convolution in the frequency domain: the authors propose applying smoothing to the frequency data representing the response of the filter, and in particular smoothing over three coefficients which is equivalent to weighting the time response by a cosine window.
The maximum of the window is assumed to correspond to the dominant coefficients of the response, which assumption is highly restrictive. The justification given by those authors for their method lies in reducing adaptation noise associated with coefficient weighting, rather than seeking an approximation to the exact solution for applying a constraint.
Other references are also mentioned, Mansour et al. [2] proposing a simplified FDAF without applying a constraint, giving rise to a considerable reduction in complexity but also to performance that is less good than that of algorithms having constraints.
Prado et al. [3] also describe a generalized version of FDAF that they refer to generalized multi-delay filter with an oversampling factor of α (GMDFα), which makes it possible to process long impulse responses with shorter data blocks by segmenting the impulse response into short blocks, thereby reducing the processing delay in the algorithm. That algorithm uses the above-mentioned constraint.
McLaughlin et al. [4] describe a modified form of the FDAF algorithm that reproduces certain aspects of GMDF, in particular segmentation of the impulse response into short blocks, and they propose a technique of applying the constraint on the various blocks that varies over time in application of a well-defined scheme (implemented by a “scheduler”), which enables complexity to be limited while preserving the benefit of the constraint to some extent.